8.2 Combinatorics
95
Stirling’s Formula
This is useful for (remarkably accurate) approximations to n factorialn!:
n factorial tilde left parenthesis 2 pi right parenthesis Superscript one half Baseline n Superscript left parenthesis n plus one half right parenthesis Baseline e Superscript negative n Baseline periodn! ∼(2π)
1
2 n(n+ 1
2 )e−n .
(8.3)
A simpler, less accurate, but easier to remember formula is
log n factorial tilde n log n minus n log n! ∼n log n −n
(8.4)
or, even more simply,
n factorial tilde n Superscript n Baseline normal e Superscript negative n Baseline periodn! ∼nne−n .
(8.5)
The Gamma Function
This can sometimes be useful since z factorial identical to normal upper Gamma left parenthesis z plus 1 right parenthesisz! ≡Γ(z + 1). According to Gauss,
normal upper Gamma left parenthesis z right parenthesis equals limit Underscript n right arrow normal infinity Endscripts ContinuedFraction n Superscript z Baseline Over z left parenthesis 1 plus z right parenthesis left parenthesis 1 plus StartFraction z Over 2 EndFraction right parenthesis midline horizontal ellipsis left parenthesis 1 plus StartFraction z Over n EndFraction right parenthesis equals StartFraction 1 Over z EndFraction product Underscript n equals 1 Overscript normal infinity Endscripts StartStartFraction left parenthesis 1 plus StartFraction 1 Over n EndFraction right parenthesis Superscript z Baseline OverOver left parenthesis 1 plus StartFraction z Over n EndFraction right parenthesis EndEndFraction equals StartFraction e Superscript minus upper C z Baseline Over z EndFraction product Underscript n equals 1 Overscript normal infinity Endscripts StartStartFraction e Superscript z divided by n Baseline OverOver left parenthesis 1 plus StartFraction z Over n EndFraction right parenthesis EndEndFractionΓ(z) = lim
n→∞
nz
z(1 + z)
(
1 + z
2
)
· · ·
(
1 + z
n
)
= 1
z
∞
∏
n=1
(
1 + 1
n
)z
(
1 + z
n
) = e−Cz
z
∞
∏
n=1
ez/n
(
1 + z
n
)
(8.6)
where upper CC is Euler’s constant.
8.2.3
Unordered Sampling Without Replacement
Suppose now that we repeat the operation carried out in the previous subsection, but
without regard to the order; that is, we simply selectrr elements from a total ofnn. Let
upper WW be the number of ways in which it can be done. After having made the selection,
we then order the elements, to arrive at the result of the previous subsection; that is,
each selection can be permuted in r factorialr! different ways. These two operations give us
the following equation:
StartFraction n factorial Over left parenthesis n minus r right parenthesis factorial EndFraction equals upper W r factorial
n!
(n −r)! = Wr!
(8.7)
The expression for upper WW, the number of combinations of rr objects out of nn, which we
shall now write as Superscript n Baseline upper C Subscript rnCr or StartBinomialOrMatrix n Choose r EndBinomialOrMatrix
(n
r
)
, follows immediately:
Superscript n Baseline upper C Subscript r Baseline equals StartBinomialOrMatrix n Choose r EndBinomialOrMatrix equals StartFraction n factorial Over r factorial left parenthesis n minus r right parenthesis factorial EndFraction commanCr =
(n
r
)
=
n!
r!(n −r)! ,
(8.8)
with StartBinomialOrMatrix n Choose 0 EndBinomialOrMatrix equals 1
(n
0
)
= 1 from the definition of 0 factorial equals 10! = 1. This is equivalent to stating that a popu-
lation of nn elements has StartBinomialOrMatrix n Choose r EndBinomialOrMatrix
(n
r
)
different subpopulations of size r less than or equals nr ≤n. Note that